/**
 * 
 */
package steffens.java.gui.treeview.model;

import java.util.Collection;

/**
 * @author Steffen Baumann
 * @version 1.0
 * 
 */
public class TreeList<T> implements Collection<T> {

	private TreePointer<T> start = null;
	private TreePointer<T> end = null;
	private TreePointer<T> parent = null;

	public TreeList() {

	}

	TreeList(TreePointer<T> parent) {
		this.parent = parent;
	}

	@Override
	public int size() {
		if (start == null)
			return 0;
		else {
			int index = 0;
			for (TreePointer<T> e = start; e != null; e = e.nextSibbling) {
				index = e.index;
			}
			return index + 1;
		}
	}

	@Override
	public boolean isEmpty() {
		if (start == null)
			return true;
		else
			return false;
	}

	@Override
	public boolean contains(Object o) {
		for (TreePointer<T> e = start; e != null; e = e.nextSibbling) {
			if (e.element.equals(o)) {
				return true;
			}
			if (e.children != null) {
				boolean childResult = e.children.contains(o);
				if (childResult) {
					return true;
				}
			}
		}
		return false;
	}

	@Override
	public TreeIterator<T> iterator() {
		return new TreeItr();
	}

	@Override
	public Object[] toArray() {
		return null;
	}

	@Override
	public <E> E[] toArray(E[] a) {
		return a;
	}

	@Override
	public boolean add(T e) {
		if (size() == 0) {
			TreePointer<T> newElement = new TreePointer<>(e);
			newElement.parent = parent;
			updateReferences(null, newElement, null, true);
		} else {
			TreePointer<T> newElement = new TreePointer<T>(e);
			newElement.parent = start.parent;
			updateReferences(end, newElement, null, true);
		}
		return true;
	}

	public boolean add(T e, int index) {
		if (index < 0 || index >= size()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		TreePointer<T> pointer = getPointerByIndex(index);
		if (pointer != null) {
			TreePointer<T> newElement = new TreePointer<T>(e);
			newElement.parent = start.parent;
			if (pointer.index == 0)
				start = newElement;
			updateReferences(pointer.prevSibbling, newElement, pointer, true);
			return true;
		} else {
			return false;
		}
	}

	public boolean addChild(T element, T child) {
		if (size() == 0) {
			return false;
		} else {
			TreePointer<T> pointer = getFirstPointerFrom(0, element);
			return addChild(pointer, child);
		}
	}
	
	public boolean addChild(int index, T child) {
		if (size() == 0) {
			return false;
		} else {
			TreePointer<T> pointer = getPointerByIndex(index);
			return addChild(pointer, child);
		}
	}
	
	public boolean addChild(int[] indizes, T child) {
		if (size() == 0) {
			return false;
		} else {
			TreePointer<T> pointer = getPointerFromChildren(indizes);
			return addChild(pointer, child);
		}
	}
	
	private boolean addChild(TreePointer<T> pointer, T child) {
		if (pointer != null) {
			if (pointer.children == null) {
				pointer.children = new TreeList<T>(pointer);
			}
			pointer.children.add(child);
			return true;
		}
		return false;
	}

	public String getPath(T element) {
		TreePointer<T> parent = getFirstPointerFrom(0, element);
		if (parent == null)
			return null;
		StringBuilder path = new StringBuilder();

		do {
			path.insert(0, "/" + parent.element);
			parent = parent.parent;
		} while (parent != null);
		return path.toString();
	}

	private TreePointer<T> getFirstPointerFrom(int offset, T element) {
		TreePointer<T> offsetStart = getPointerByIndex(offset);

		for (TreePointer<T> p = offsetStart; p != null; p = p.nextSibbling) {
			if (p.element.equals(element)) {
				return p;
			}
			if (p.children != null && !p.children.isEmpty()) {
				TreePointer<T> tempPointer = p.children.getFirstPointerFrom(0, element);
				if (tempPointer != null) {
					return tempPointer;
				}
			}
		}
		return null;
	}

	@Override
	public boolean remove(Object o) {
		if (size() == 0) {
			return false;
		} else {
			for (TreePointer<T> p = start; p != null; p = p.nextSibbling) {
				if (p.element.equals(o)) {
					if (p.prevSibbling != null && p.nextSibbling != null) {
						updateReferences(p.prevSibbling, p.nextSibbling, p.nextSibbling.nextSibbling, true);
						return true;
					}
					if (p.prevSibbling != null && p.nextSibbling == null) {
						updateReferences(p.prevSibbling, null, null, false);
						return true;
					}
					if (p.prevSibbling == null && p.nextSibbling != null) {
						updateReferences(null, p.nextSibbling, p.nextSibbling.nextSibbling, true);
						start = p.nextSibbling;
						return true;
					}
					if (p.prevSibbling == null && p.nextSibbling == null) {
						this.start = null;
						if (parent != null) {
							this.parent.children = null;
						}

					}
					return true;
				}
			}
		}
		return false;
	}

	private void updateReferences(TreePointer<T> prev, TreePointer<T> current, TreePointer<T> next,
			boolean updateIndizes) {
		if (prev != null) {
			prev.nextSibbling = current;
			if (prev.nextSibbling == null) {
				end = prev;
			}
		}
		if (current != null) {
			current.prevSibbling = prev;
			if (current.prevSibbling == null) {
				start = current;
			}
			current.nextSibbling = next;
			if (current.nextSibbling == null) {
				end = current;
			}
		}
		if (next != null) {
			next.prevSibbling = current;
		}
		if (updateIndizes) {
			updateIndixAndParent();
		}

	}

	public int indexOf(T element) {
		return indexOf(0, element);
	}

	public int indexOf(int offset, T element) {
		TreePointer<T> offsetStart = getPointerByIndex(offset);
		for (TreePointer<T> e = offsetStart; e != null; e = e.nextSibbling) {
			if (e.element.equals(element)) {
				return e.index;
			}
		}
		return -1;
	}

	public T getElement(int index) {
		TreePointer<T> pointer = getPointerByIndex(index);
		if (pointer != null) {
			return pointer.element;
		} else {
			return null;
		}
	}

	public T getElement(int[] indizes) {
		TreePointer<T> pointer = getPointerFromChildren(indizes);
		if (pointer == null) {
			return null;
		} else {
			return pointer.element;
		}
	}

	private TreePointer<T> getPointerFromChildren(int[] indizes){
		TreeList<T> list = this;
		TreePointer<T> pointer = null;
		for (int i = 0; i < indizes.length; i++) {
			if (list == null) {
				return null;
			}
			pointer = list.getPointerByIndex(indizes[i]);
			if (pointer != null) {
				list = pointer.children;
			} else {
				return null;
			}
		}
		return pointer;
	}
	
	private TreePointer<T> getPointerByIndex(int index) {
		for (TreePointer<T> e = start; e != null; e = e.nextSibbling) {
			if (e.index == index) {
				return e;
			}
		}
		return null;
	}

	public boolean addAll(Collection<? extends T> c, int index) {
		TreeList<T> list = new TreeList<T>();
		for (T e : c) {
			list.add(e);
		}
		return addTreeList(index, list);
	}

	public boolean addTreeList(TreeList<T> treeList) {
		if (treeList == null) {
			return false;
		} else if (this.size() == 0) {
			start = treeList.start;
			end = start;
		} else {
			addTreeList(end, null, treeList);
		}
		return true;
	}

	public boolean addTreeList(int index, TreeList<T> treeList) {
		if (treeList == null) {
			return false;
		} else if (this.size() == 0) {
			start = treeList.start;
			end = start;
		} else {
			TreePointer<T> pointer = getPointerByIndex(index);
			if (pointer == null)
				return false;
			addTreeList(pointer.prevSibbling, pointer, treeList);
		}
		return true;
	}

	private void addTreeList(TreePointer<T> pointerStart, TreePointer<T> pointerEnd, TreeList<T> treeList) {
		updateReferences(pointerStart, treeList.start, treeList.start.nextSibbling, false);
		updateReferences(treeList.end.prevSibbling, treeList.end, pointerEnd, true);
	}

	public TreeList<T> getChildren(int offset, T element) {
		return getChildren(getFirstPointerFrom(0, element));
	}

	public TreeList<T> getChildren(T element) {
		return getChildren(0, element);
	}

	public TreeList<T> getChildren(int index) {
		return getChildren(getPointerByIndex(index));
	}

	private TreeList<T> getChildren(TreePointer<T> pointer) {
		if (pointer != null) {
			return pointer.children;
		} else {
			return null;
		}
	}

	private void updateIndixAndParent() {
		int index = 0;
		for (TreePointer<T> e = start; e != null; e = e.nextSibbling) {
			e.index = index;
			e.parent = this.parent;
			index += 1;
		}
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c) {
			if (!contains(o)) {
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		return addAll(c, end.index);
	}

	public boolean addAllChildren(T element, Collection<? extends T> c) {
		TreePointer<T> pointer = getFirstPointerFrom(0, element);
		return addAllChildren(pointer, c);
	}

	private boolean addAllChildren(TreePointer<T> pointer, Collection<? extends T> c) {
		if (pointer != null) {
			if (pointer.children == null) {
				pointer.children = new TreeList<T>(pointer);
			}
		}
		return pointer.children.addAll(c, 0);
	}

	public boolean addAllChildren(int index, Collection<? extends T> c) {
		TreePointer<T> pointer = getPointerByIndex(index);
		return addAllChildren(pointer, c);
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean result = false;
		for (Object o : c) {
			do {
				result |= remove(o);
			} while (contains(o));
		}
		return result;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		TreeList<T> list = retainAllPointer(this, this.parent, c);
		this.start = list.start;
		this.end = list.end;
		return false;
	}

	private TreeList<T> retainAllPointer(TreeList<T> list, TreePointer<T> parent, Collection<?> c) {
		TreeList<T> newTree = new TreeList<T>(parent);
		for (TreePointer<T> pointer = list.start; pointer != null; pointer = pointer.nextSibbling) {
			if (!c.contains(pointer.element)) {
				if (pointer.children != null) {
					newTree.addTreeList(retainAllPointer(pointer.children, list.parent, c));
				}
			} else {
				newTree.add(pointer.element);
				if (pointer.children != null) {
					newTree.end.children = retainAllPointer(pointer.children, newTree.end, c);
				}
			}
		}
		if (newTree.isEmpty()) {
			return null;
		} else {
			return newTree;
		}
	}

	@Override
	public void clear() {
		start = null;
		end = null;
	}

	private static class TreePointer<T> {
		private int index = -1;
		private T element = null;
		TreePointer<T> parent = null;
		TreePointer<T> prevSibbling = null;
		TreePointer<T> nextSibbling = null;
		TreeList<T> children = null;

		public TreePointer(T element) {
			this.element = element;
		}
	}

	public class TreeItr implements TreeIterator<T> {
		private TreePointer<T> next = start;
		private TreePointer<T> prev = null;
		private TreePointer<T> current = null;

		public boolean hasChildren() {
			if (current.children == null)
				return false;
			return !current.children.isEmpty();
		}

		public TreeList<T> getChildren() {
			return current.children;
		}

		public boolean hasNext() {
			if (next != null) {
				return true;
			}
			return false;
		}

		public T next() {
			TreePointer<T> temp = next;
			updatePositions(next.prevSibbling, next, next.nextSibbling);
			return temp.element;
		}

		public void remove() {
			if (next == null && prev == null) {
				current = null;
			} else if (next == null && prev != null) {
				updatePositions(prev.prevSibbling, prev, null);
			} else {
				updatePositions(prev, next, next.nextSibbling);
			}
		}

		public boolean hasPrevious() {
			if (prev != null) {
				return true;
			} else {
				return false;
			}
		}

		public T previous() {
			TreePointer<T> temp = next;
			updatePositions(prev.prevSibbling, prev, prev.nextSibbling);
			return temp.element;
		}

		private void updatePositions(TreePointer<T> prev, TreePointer<T> current, TreePointer<T> next) {
			this.prev = prev;
			this.next = next;
			this.current = current;
		}

		@Override
		public int getIndex() {
			return current.index;
		}
	}
}
